Sliding Window
This is a REALLY good post: https://leetcode.com/tag/two-pointers/discuss/1122776/Summary-of-Sliding-Window-Patterns-for-Subarray-Substring https://leetcode.com/tag/sliding-window/discuss/490184/Sliding-Window-Understanding-the-pattern.-Resources
Overview
- Intuition/Idea
- We have a "window" of 2 pointers,
leftandright, and we keep increasing the right pointer- If the element at the right pointer makes the window not valid, we keep moving the left pointer to shrink the window until it becomes valid again
- Then, we update the global min/max with the result from the valid window
- To check if it is valid, we need to store the "state" of the window (ex: frequency of letters, num of distinct elements, etc)
- It's important that we be able to define the state of the window, this state need to be valid at all time and move the window accordingly when it becomes invalid till it becomes valid again
- We have a "window" of 2 pointers,
- This can be considered as the extension of [[3. Two Pointer]]
- Template:
for(right = 0; right < n; right++):
update window with element at right pointer
while (condition not valid):
remove element at left pointer from window, move left pointer to the right
update global max
When it fails
- If knowing one element at the edges of the window does not tell you how to update the state of the window, or whether it becomes valid
- If adding one element could either increase or decrease the window' state
- If it is hard to check whether adding or remove from only one end at a time would ever make it valid
- [General summary of what kind of problem can/ cannot solved by Two Pointers](https://leetcode.com/problems/subarray-sum-equals-k/solutions/301242/General-summary-of-what-kind-of-problem-can-cannot-solved-by-Two-Pointers/)
Patterns
Length of Substring/Subarray questions
def lengthOfLongestSubstring(self, s: str) -> int:
cur_set = set()
left = 0
res = 0
for right in range(len(s)):
if s[right] not in cur_set:
cur_set.add(s[right])
else:
while s[right] in cur_set:
cur_set.remove(s[left])
left += 1
cur_set.add(s[right])
res = max(res, right - left + 1)
return res
Max/Min Length Sliding Window questions
- May look different from the previous pattern, but are just worded differently, the main idea is the same904. Fruit Into Baskets
- [1004. Max Consecutive Ones III](https://leetcode.com/problems/max-consecutive-ones-iii/)
def totalFruit(self, fruits: List[int]) -> int:
basket = {}
res = 0
left = 0
for right in range(len(fruits)):
if fruits[right] in basket:
basket[fruits[right]] += 1
elif len(basket) < 2 and fruits[right] not in basket:
basket[fruits[right]] = 1
else:
while len(basket) == 2:
basket[fruits[left]] -=1
if basket[fruits[left]] == 0:
del basket[fruits[left]]
left += 1
basket[fruits[right]] = 1
res = max(res, right-left+1)
return res
424. Longest Repeating Character Replacement
def characterReplacement(self, s: str, k: int) -> int:
count = collections.defaultdict(lambda: 0)
res = 0
left = 0
for right in range(len(s)):
count[s[right]] += 1
major = max(count.values())
while (right- left + 1) - major > k:
count[s[left]] -= 1
# we don't need to update the major values as
# keeping the major while incrementing the left will make the loop break earlier => shrink more not less
left += 1
res = max(res, right - left + 1)
return res
https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
res = 1
left = 0
for right in range(1, len(nums)):
if abs(nums[right] - nums[left]) <= 2 * k:
res = max(res, right - left + 1)
else:
while abs(nums[right] - nums[left]) > 2*k:
left += 1
return res
https://leetcode.com/problems/take-k-of-each-character-from-left-and-right
def takeCharacters(self, s: str, k: int) -> int:
chrDict = collections.Counter(s)
for c in ['a', 'b', 'c']:
if chrDict[c] < k:
return -1
curDict = collections.defaultdict(int)
res = 0
left = 0
for right in range(len(s)):
curDict[s[right]] += 1
while left <= right and (
chrDict["a"] - curDict["a"] < k or
chrDict["b"] - curDict["b"] < k or
chrDict["c"] - curDict["c"] < k
):
curDict[s[left]] -= 1
left += 1
res = max(res, right - left + 1)
return len(s) - res
https://leetcode.com/problems/minimum-window-substring
- Straight forward sliding window, not that different from every other sliding window probs
def minWindow(self, s: str, t: str) -> str:
counter = collections.Counter(t)
current = collections.defaultdict(int)
res = ""
minLength = float("inf")
left = 0
def checkContains():
for c, count in counter.items():
if c not in current or current[c] < count:
return False
return True
for right in range(len(s)):
current[s[right]] += 1
while checkContains():
if right - left + 1 < minLength:
minLength = right - left + 1
res = s[left : right + 1]
current[s[left]] -= 1
left += 1
return res
Number of Subarrays questions
- Before, we were finding the min/max length of subarray, now we want the number of subarrays
930. Binary Subarrays with Sum
https://leetcode.com/problems/subarray-product-less-than-k/
- **For these type of questions, we usually get ask to return the number of valid subarrays, we can calculate these easily by
res += right - left + 1, the reason being by introducing a new element atnums[right], we are adding that many new valid subarrays. E.g: [1,2] has 3 valid subarrays and [1,2,3] has 6
Prefixed Sliding Windows
- TBD
- 930. Binary Subarrays with Sum
- 992. Subarrays with K different integers
- Count Number of Nice Subarrays
- Subarrays containing all three characters
Sliding Window + Heap
- The core idea of using [[8. Heap]] in sliding window problems comes from their ability to efficiently maintain a sorted order or elements while allowing dynamic updates. This is particularly useful when we need to track maximum or minimum values in a moving range of elements.
Templates: When using heaps in sliding window problems, we typically store elements as tuples or pairs containing both the value and its position.
- The position information is crucial because it helps us determine whether an element is still within our current window
- Using heap, there's no easy way to remove an element given its value
- We usually have to store index/position to identify the boundary of the element in the heap
- We need to maintain the boundary and only pop the element if it's out of boundary
# Example pattern
heap = [] # Store (-value, index) pairs
left = 0 # Left boundary of window
# 1. Add new elements
heapq.heappush(heap, (-new_value, index))
# 2. Remove outdated elements
while heap and heap[0][1] < left: # Index < left boundary
heapq.heappop(heap)
# 3. Get current answer
current_max = -heap[0][0] # Negate back to get original value
https://leetcode.com/problems/sliding-window-maximum/
- Direct application
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
maxHeap = []
res = []
left = 0
for i in range(k):
heapq.heappush(maxHeap, (-nums[i], i))
res.append(-maxHeap[0][0])
for right in range(k, len(nums)):
heapq.heappush(maxHeap, (-nums[right], right))
while right - left + 1 > k:
left += 1
while maxHeap[0][1] < left:
heapq.heappop(maxHeap)
res.append(-maxHeap[0][0])
return res
- Very good questions that no one seems to talk about
def longestSubarray(self, nums: List[int], limit: int) -> int:
res = 0
left = 0
minHeap = []
maxHeap = []
for right in range(len(nums)):
heapq.heappush(minHeap, (nums[right], right))
heapq.heappush(maxHeap, (-nums[right], right))
while -maxHeap[0][0] - minHeap[0][0] > limit:
left = min(maxHeap[0][1], minHeap[0][1]) + 1
while maxHeap[0][1] < left:
heapq.heappop(maxHeap)
while minHeap[0][1] < left:
heapq.heappop(minHeap)
res = max(res, right - left + 1)
return res
https://leetcode.com/problems/meeting-rooms-iii
https://leetcode.com/problems/minimum-cost-to-make-array-equal
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k